
        <html>
			<head>
			     <title>逆向被虚拟机所保护的二进制文件 - 左懒</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/9616">http://drops.wooyun.org/tips/9616</a></h1>
				
      <p>
        <p>From: <a href="http://resources.infosecinstitute.com/reverse-engineering-virtual-machine-protected-binaries/">http://resources.infosecinstitute.com/reverse-engineering-virtual-machine-protected-binaries/</a></p>

<h1>0x00 简介</h1>

<hr />

<p>在代码混淆当中，虚拟机被用于在一个程序上运行不同机器指令集。例如虚拟机可以让32位的x86架构机器上运行ARM指令集。用于代码混淆的虚拟机跟那种普通的，能运行操作系统的虚拟机完全不同（如：VMware），前者只用于执行有限的指令做一些特定的任务。</p>

<p>在了解相关代码混淆器的虚拟机指令集执行机制后，逆向工程一个使用该指令集的虚拟机所保护程序还是比较容易的。只需要花费少量的时间来研究一下这个架构的指令集操作码。然而悲剧的是，现在的虚拟机代码混淆器大多数都使用自定义指令集。换句话说，每个指令都被赋予一个自定义的操作码（通常都是随机的）和自定义的格式，逆向人员需要逆向解码每个操作码的含义。这简直会玩死人！举个栗子，让我们来看看32位的x86指令集和我们将在本文中介绍的自定义指令集之间的区别：</p>

<!--more-->

<p><img src="http://static.wooyun.org//drops/20151014/2015101405202361521picture1.png" alt="" /></p>

<p>很明显，这些指令都是把第二个操作数指定的内存字节赋值到第一个操作数的寄存器当中。然而这两条指令的二进制操作码表示却并不相同，其中第二条指令的0x56操作码完全是一个随机数字。两条指令的第二个字节都表示操作码需要用到的寄存器，其中每4位表示一个寄存器。</p>

<p>在进入逆向工程实例之前，我们得先知道基于虚拟机代码混淆技术幕后的工作原理：虚拟机启动后首先第一件事便在它的进程虚拟地址空间中申请一块“address space”，换句话说，它申请所需的内存空间，栈和寄存器。然后，虚拟机加载操作码文件并执行。代码的执行是由一个VM loop完成的。在这个loop当中，虚拟机的处理器解析每个预定的操作码和操作数，然后根据指令集迭代执行。直到VM loop遇到一个指定的退出操作码。</p>

<h1>0x01 举个例子</h1>

<hr />

<p>为此我花了一些时间用C语言写了一个自定指令集的虚拟机，完整的源代码可以在这篇文章最后获得。正如你所猜的，单独一个虚拟机是做不了任何事情的。这也是我为什么还写了这么一个CrackMe小程序。另外我诚挚邀请大家也给这个小家伙添加更多的功能吧！</p>

<p>在前言中提到过的，这个虚拟机使用一套自定的指令集，并由虚拟机在初始化阶段后把操作码文件加载到“address space”。</p>

<p>让我们确保操作码文件和虚拟机在同一个目录，然后执行。随便输入一串密码可以看到：</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405202532806picture2.png" alt="" /></p>

<p>密码验证失败！</p>

<p>我们现在的目标就是给这个程序找出正确的密码。先从看一下这个操作码文件(vm_file)开始，用十六进制编辑器打开它：</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405202730593picture3.png" alt="" /></p>

<p>可以看到，在vm_file文件有诸如”Right pass!“，”Wrong pass!“和”Password:“的字符串。接下来开始逆向这个虚拟机，用IDA打开它。</p>

<p>IDA打开虚拟机之后我们直接定位到VM loop的虚拟地址：0x00401334。下图显示了这个程序相当庞大，但既然找到正确的入口点那我们肯定有办法搞定它。</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405203054964picture4.png" alt="" /></p>

<p>让我们来看看入口函数执行了哪些指令：</p>

<pre><code>    push    ebp
    push    edi
    push    esi
    push    ebx
    sub     esp, 2Ch
    mov     esi, [esp+3Ch+arg_0]
    mov     ebx, [esp+3Ch+arg_4]
    mov     ax, [ebx+0Ah]
    lea     ebp, [esi+1200h]
loc_40134D: ; This is where the loop starts
    movzx edx, ax
    mov     cl, [esi+edx]
    lea     edx, [eax+1]
    mov     [ebx+0Ah], dx
    sub     ecx, 10h
    cmp     cl, 0E1h     ; switch 226 cases
    jbe     short loc_40136C
</code></pre>

<p>”mov cl, [esi+edx]“指令读取一个字节到CL，很显然CL寄存器只包含了操作码。该操作码是通过ESI和EDX两个寄存器进行定位的。从前面可以清楚地看到EDX只包含了一个WORD（16 bit）而ESI包含了DWORD（32 bit）。所以，ESI实际上是指向VM代码段，而DX指向我们的虚拟机当前指令的指针（文件中当前操作码的index）。</p>

<p>在正确读入字节之后我们注意到DX寄存器的值被保存到[EBX + 0AH]。这位置是虚拟机分配的寄存器空间。我们现在知道EBX寄存器指示着ESI寄存器所指向的文件数据在内存中的位置。</p>

<p>在比较之前，我们注意到编译器使用了编译优化：在访问switch table之前的每个操作码的值减去0x10。</p>

<pre><code>loc_40136C:
    movzx ecx, cl
    jmp     ds:switchTable[ecx*4] ; switch jump
</code></pre>

<p>该switch table虽然相当大，但它可以更快地计算出动态地址。你可以在Win32下用OllyDbg或IDA运行调试这个程序。</p>

<h1>0x02 第一条指令</h1>

<hr />

<p>第一个switch带我们跳到一个小过程当中：</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405203172489picture5.png" alt="" /></p>

<p>我们现在处于“case 0x18”这个操作码，因为编译器增加了一个减法操作优化这段代码。如果你现在回去检查一下vm_file的话可以发现第一个字节就是0x18。这个操作码似乎需要一些操作数，所以VM多读取一个字节到DX寄存器。下一步，VM的指令指针[EBX+0AH]更新为EAX+2，这意味着IP(instruction pointer)指向下一个字节。之后，读取到的字节跟3比较，如果大于3则离开循环并抛出一个异常。但在我们的例子中是不会抛出异常的，因为二进制文件中该操作数等于0x01，因此程序不会发生跳转。接着我们到达这里：</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405203356055picture6.png" alt="" /></p>

<p>提醒你一下，EBX是指向虚拟机的寄存器数组的指针，所以第一条指令把[EBX+1*2]（第二个寄存器）初始化为0。</p>

<p>现在，我们有足够的信息可以判断VM包含了4个寄存器，我们可以称之为R0，R1，R2，R3。</p>

<p>剩下的代码从文件加载2个字节（大端序的0x250）的数据存放到R1寄存器中。接着，VM的指令指针会指向下一条指令，也就是在文件的0x04偏移处。最后，jmp跳转到loc_40134D的VM loop循环处开始下一条指令的执行。</p>

<p>直到现在，我们只能知道第一条指令是什么，它只是一条简单的mov指令。这条指令可以重写为下面的格式：</p>

<pre><code>    MOV R1, 250H
</code></pre>

<h1>0x03 第二条指令</h1>

<hr />

<p>让我们来看看下个操作码（0xAF）:</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405203417139picture7.png" alt="" /></p>

<p>第一个代码块跟之前的mov指令一样。显然，这是需要用到一个寄存器作为操作数的典型代码，在我们的例子当中，它使用的是R1(0x01)寄存器。下一步它访问[EBX+0CH]的寄存器。我们知道这个寄存器肯定不是R0，R1，R2，R3。因为R3被存储在[EBX+6]。我们也知道这不是IP指令指针，因为它位于[EBX+0AH]。所以要弄清楚这个寄存器是什么，我们需要回去检查它在主函数中的初始化：</p>

<pre><code>.text:00402703 mov     word ptr [eax+0Ch], 256
</code></pre>

<p>回到我们分析处，我们注意到获取到这个寄存器的值后做减一操作，然后再跟0xFFFF做比较。因为该寄存器被初始化为256，所以在该寄存器的值为0并减一之前是不会等于0xFFFF的。如果该寄存器等于0xFFFF，那么VM将退出循环。因为我们这是第一次执行，所以断定[EBX+0CH]肯定等于255。</p>

<p>接下来两条指令读取R1（0x250）的值保存到DX寄存器。接着就可以看到一条有趣的指令：</p>

<pre><code>mov [esi+eax*2+1000h], dx
</code></pre>

<p>如果你还记得的话，ESI是指向代码和数据区域的基址。此外，ESI+1000H跨度了4K的地址空间。因此，我们可以假设，ESI+1000H是指向一个不同的“section”的VM“address space”。</p>

<p>我们可以用伪代码重述一下这个操作：</p>

<pre><code>#!c
WORD section[256];
[…]
section[ –reg ] = R1;
</code></pre>

<p>看起来这似乎是一个栈结构，R1寄存器的值被保存到栈指针减一后所在的位置。我们可以大胆地假设0xAF操作码代表PUSH指令。因此，这条操作码指令的含义可以理解为：PUSH R1。</p>

<p>现在我们知道[EBX+0CH]是VM的栈指针，栈空间为256*sizeof(uint16_t)。此外，如果你想把VM的栈指针和x86架构的机器栈指针做比较，可以看到VM的栈指针仅仅是一个array的index，而x86机制的栈指针是一个寄存器（ESP）。</p>

<h1>0x04 第三条指令</h1>

<hr />

<p>接着第三个操作码（0xC2）：</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405203621995picture8.png" alt="" /></p>

<p>这个操作码的含义似乎是在读取栈顶的一个WORD数据。但在读取之前它先检查栈是否为空，如果是，则抛出一个VM异常。因为之前已经有一个值PUSH进去了，所以我们知道这个栈不为空。把栈顶的数据保存到DX寄存器后，栈指针+1。我们还知道DX的值现在为0x250（属于代码和数据区域的一部分）。随后，确保栈顶的值不会超过0x1000（address space的尺寸）。接下来把[ESI+DX]指向的字符串作为的参数调用printf。在我们这个例子当中，vm_file第0x250个字节保存的字符串是“Password:”，它将被打印到屏幕上。</p>

<p>我们可以得出这样的结论：0xC2指令需要把字符串偏移PUSH到栈上，然后POP出来printf它。</p>

<p>正如你所见，在这完成逆向这些操作码之后我们已经到达打印“Password:”的代码上。你可能已经注意到我们可以用单一的指令简化每个操作码所代表的执行动作。接下来，我们不采用逐步的分析方式来分析这些操作码了。但是现在的你应该能够逆向工程一个被虚拟机所保护的程序，甚至打造一个属于自己的虚拟机保护程序。</p>

<h1>0x05 破解密码</h1>

<hr />

<p>下面给出如何快速找到正确密码的方式：</p>

<p>用十六进制编辑器打开vm&#95;file文件，取出0x80到0x17F偏移处的256个随机字节，我们可以把它称之为Random。将用户输入的密码每个字节都跟Random异或运行，然后跟vm&#95;file文件在0x240偏移处预定的数组做比较。</p>

<p>我在下面引用一节中已经给出了一个密码生成器。编译执行它便可获得正确的密码：</p>

<p><img src="http://static.wooyun.org//drops/20151014/2015101405203757665picture9.png" alt="" /></p>

<h1>0x06 引用</h1>

<hr />

<ul>
<li><a href="https://gist.github.com/SouhailHammou/6b4069b07e538a48bb70">VM source code</a></li>
<li><a href="https://mega.nz/#!sVwxEKjD!LOmwg8_XFWMV0dMRcLdea4OQ6Bluo8bUpqXyZdWbLuw">Opcodes file (vm_file)</a></li>
<li><a href="https://gist.github.com/SouhailHammou/d306c9127df6c53d2eda">Hex dump of vm_file for those who don’t want to download it</a></li>
<li><a href="https://gist.github.com/SouhailHammou/71c06a12c3d3cebd437b">Solution code</a></li>
</ul>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          